public class MedianFinder {
	private Heap<Integer> minHeap;
	private Heap<Integer> maxHeap;

	public MedianFinder() {
		minHeap = new MinHeap<Integer>();
		maxHeap = new MaxHeap<Integer>();
	}

	public Integer getMedian() {
		if (minHeap.size() == 0 && maxHeap.size() == 0)
			return Integer.MAX_VALUE;

		if (minHeap.size() == maxHeap.size())
			return (minHeap.getRoot() + maxHeap.getRoot()) / 2;
		else
			return maxHeap.getRoot();
	}

	public void insert(int val) {
		Integer median = getMedian();

		if (val <= median) {
			if (minHeap.size() == maxHeap.size())
				maxHeap.add(val);
			else {
				if (val < maxHeap.getRoot()) {
					int max = maxHeap.removeRoot();
					maxHeap.add(val);
					minHeap.add(max);
				} else
					minHeap.add(val);
			}
		} else {
			if (minHeap.size() == maxHeap.size()) {
				if (val > minHeap.getRoot()) {
					int min = minHeap.removeRoot();
					maxHeap.add(min);
					minHeap.add(val);
				} else
					maxHeap.add(val);
			} else
				minHeap.add(val);
		}
	}
}

abstract class Heap<T> {

	public abstract void add(T val);

	public int size() {
		return -1;
	}

	public T getRoot() {
		return null;
	}

	public T removeRoot() {
		return null;
	}
}

class MinHeap<T> extends Heap<T> {

	@Override
	public void add(T val) {
	}

}

class MaxHeap<T> extends Heap<T> {

	@Override
	public void add(T val) {
	}

}